package org.lyc.dp;

/**
 * 寻找数组的中心下标
 * 前缀和
 * https://leetcode.cn/problems/find-pivot-index/
 *
 * @author Liu Yicong
 * @date 2024/2/29
 */
public class JPivotIndex {

	//prefixSum = {0,1,8,11,17,22,28}
	static int[] nums1 = {1, 7, 3, 6, 5, 6};

	//prefixSum = {0,1,3,6}
	static int[] nums2 = {1, 2, 3};

	//prefixSum = {0,2,3,2}
	static int[] nums3 = {2, 1, -1};
	static int[] nums4 = {-1, -1, 0, 0, -1, -1};


	public static void main(String[] args) {
		System.out.println(pivotIndex(nums1));
		System.out.println(pivotIndex(nums2));
		System.out.println(pivotIndex(nums3));
		System.out.println(pivotIndex(nums4));
	}

	public static int pivotIndex(int[] nums) {
		int n = nums.length;
		int[] prefixSum = new int[n + 1];
		prefixSum[0] = 0;
		for (int i = 1; i <= n; i++) {
			prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
		}
		for (int i = 1; i <= n; i++) {
			if (prefixSum[n] - prefixSum[i] == prefixSum[i - 1]) {
				return i - 1;
			}
		}
		return -1;
	}
}
